// 518 零钱兑换II
// https://leetcode.cn/problems/coin-change-ii/description/
// 动态规划
/**
 * 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。 
题目数据保证结果符合 32 位带符号整数。

示例 1：
输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：
输入：amount = 10, coins = [10] 
输出：1
 

提示：
1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000
 */

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function (amount, coins) {
    const dp = new Array(amount + 1).fill(0);

    /**
     * 初始化dp[0] = 1
     * 为什么？
     * 因为 0 元可以有一种组合，就是不选择任何硬币
     * 所以 dp[0] = 1
     *
     * 主要是测试用例里要求 coins=[7],amount=0时，change(0,[7]) = 1
     */
    dp[0] = 1;

    /**
     * 下方需要构建双层循环，一层循环amount，另一层循环coins
     * 这两层循环顺序是有说法的，应该先循环coins，再循环amount，不然会导致重复的组合进入dp数组
     * 代码最下方会给出外层amount,内层coins的错误循环
     */
    for (let i = 0; i < coins.length; i++) {
        const coin = coins[i];
        for (let j = 1; j <= amount; j++) {
            if (j - coin < 0) {
                continue;
            }

            if (j === coin) {
                dp[j] += 1;
                continue;
            }

            /**
             * dp[amount]是渐渐需要经过coin的迭代，渐渐累加的
             * 举例：
             * 假如coins = [1,2,5], amount = 5，
             * 当i=0，j=5时，即coin=1, dp[5] = 1 => 因为此时放入的组合是[1,1,1,1,1]
             */
            dp[j] += dp[j - coin];
        }
    }

    console.log(dp[amount]);
    return dp[amount];
};

// 错误循环
// var change = function (amount, coins) {
//     const dp = new Array(amount + 1).fill(0);
//     dp[0] = 1;
//     for (let i = 1; i <= amount; i++) {
//         let findSelf = false;
//         for (let j = 0; j < coins.length; j++) {
//             let coin = coins[j];
//             if (i - coin < 0) {
//                 continue;
//             }

//             if (i === coin) {
//                 dp[i] += 1;
//                 continue;
//             }

//             dp[i] += dp[i - coin];
//         }
//     }

//     console.log(dp[amount]);
//     return dp[amount];
// };

change(5, [1, 2, 5]); // 4
change(3, [2]); // 0
change(10, [10]); // 1
